package com.chengzhi.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @description:
 * @author: ruanchengzhi
 * @create: 2020-04-16 19:09
 **/
public class StringDemo {

    public static void main(String[] args) {
//        String[] ints = new String[]{"i", "love", "leetcode", "i", "love", "coding"};
//        List<String> strings = topKFrequent(ints, 2);
//        System.out.println(strings);
//        System.out.println(isValid("{[]}"));
//        System.out.println(longestValidParentheses(")()())"));
//        System.out.println(reverseWords("  Bob    Loves  Alice   "));
        System.out.println(isAnagram("anagram", "nagaram"));
    }

    public static String reverseWords(String s) {
        if (null == s || s.length() == 0) {
            return null;
        }
        LinkedList<String> list = new LinkedList<>();
        String[] s1 = s.split(" ");
        for (int i = 0; i < s1.length; i++) {
            String temp = s1[i];
            if (null != temp && !temp.equals("")) {
                list.add(temp);
            }
        }
        Collections.reverse(list);
        return list.stream().collect(Collectors.joining(" "));
    }

    /**
     * 32. 最长有效括号
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        if (null == s || s.length() == 0) {
            return 0;
        }
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

    /**
     * 20. 有效的括号
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if (null == s || s.length() == 0) {
            return false;
        }
        Map<Character, Character> replaceMap = new HashMap<>();
        replaceMap.put('(', ')');
        replaceMap.put('[', ']');
        replaceMap.put('{', '}');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.isEmpty()) {
                stack.add(c);
            } else {
                Character key = stack.peek();
                if (replaceMap.containsKey(key) && replaceMap.get(key).equals(c)) {
                    stack.pop();
                } else {
                    stack.add(c);
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }


    /**
     * 给一非空的单词列表，返回前 k 个出现次数最多的单词。
     * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
     *
     * @param words
     * @param k
     * @return: java.util.List<java.lang.String>
     * @author: ruanchengzhi
     * @date: 2020/9/23
     */
    public static List<String> topKFrequent(String[] words, int k) {
        int length = words.length;
        if (length == 0 || length < k) {
            return new ArrayList<>();
        }
        Map<String, Integer> compareMap = new TreeMap<>();
        for (String word : words) {
            compareMap.put(word, compareMap.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> heap = new PriorityQueue<>(
                (w1, w2) -> compareMap.get(w1).equals(compareMap.get(w2)) ?
                        w2.compareTo(w1) : compareMap.get(w1) - compareMap.get(w2));

        for (String word : compareMap.keySet()) {
            heap.offer(word);
            if (heap.size() > k) heap.poll();
        }

        List<String> ans = new ArrayList();
        while (!heap.isEmpty()) ans.add(heap.poll());
        Collections.reverse(ans);
        return ans;

    }

    /**
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
     * 你必须原地修改输入数组、使用 O(1) 的额外空间
     *
     * @param s
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/8/17
     */
    public static void reverseString(char[] s) {
        int length = s.length;
        if (length == 0) {
            return;
        }
        int mid = length / 2;
        int index = 1;
        for (int i = 0; i < mid; i++) {
            char temp = s[s.length - index];
            s[s.length - index] = s[i];
            s[i] = temp;
            index++;
        }
    }


    /**
     * 实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。
     * A-Z 65-90，a-z 97-122
     *
     * @param str
     * @return: java.lang.String
     * @author: ruanchengzhi
     * @date: 2020/8/17
     */
    public static String toLowerCase(String str) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            int c = str.charAt(i);
            if (c >= 65 && c <= 90) {
                int val = c + 32;
                builder.append((char) val);
            } else {
                builder.append((char) c);
            }
        }
        return builder.toString();
    }

    /**
     * 给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
     *
     * @param s
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/8/17
     */
    public static int lengthOfLastWord(String s) {
        int length = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                length++;
            } else if (length != 0) {
                return length;
            }
        }
        return length;
    }

    /**
     * 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
     * S 和 J 最多含有50个字母。
     * J 中的字符不重复。
     *
     * @param J
     * @param S
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/8/17
     */
    public int numJewelsInStones(String J, String S) {
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < J.length(); i++) {
            list.add(J.charAt(i));
        }
        int temp = 0;
        for (int i = 0; i < S.length(); i++) {
            if (list.contains(S.charAt(i))) {
                temp++;
            }
        }
        return temp;
    }

    public static int numJewelsInStones1(String J, String S) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < J.length(); i++) {
            map.put(J.charAt(i), 0);
        }
        for (int i = 0; i < S.length(); i++) {
            if (map.containsKey(S.charAt(i))) {
                map.merge(S.charAt(i), 1, (v1, v2) -> v1 + v2);
            }
        }
        return map.values().stream().collect(Collectors.summingInt(t -> t));
    }

    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""
     *
     * @param strs
     * @return: java.lang.String
     * @author: ruanchengzhi
     * @date: 2020/8/17
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String temp = strs[0];
        if (temp.length() == 0) {
            return "";
        }
        for (int i = 1; i < strs.length; i++) {
            String val = strs[i];
            if (val.length() == 0) {
                return "";
            }
            int length = temp.length();
            int valLength = 0;
            while (valLength <= length - 1) {
                if (valLength > val.length() - 1) {
                    temp = temp.substring(0, valLength);
                    break;
                }
                if (temp.charAt(valLength) == val.charAt(valLength)) {
                    valLength++;
                    continue;
                } else {
                    temp = temp.substring(0, valLength);
                    break;
                }
            }
        }
        return temp;
    }

    /**
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * 示例1:
     * <p>
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     * <p>
     * 输入: s = "rat", t = "car"
     * 输出: false
     *
     * @param s
     * @param t
     * @return: boolean
     * @author: ruanchengzhi
     * @date: 2020/4/16
     */
    public static boolean isAnagram(String s, String t) {
        if (null == s || null == t || s == "" || t == "") {
            return false;
        }
        List<Character> characterList = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            characterList.add(s.charAt(i));
        }
        List<Character> characterLists = new ArrayList<>();
        for (int i = 0; i < t.length(); i++) {
            characterLists.add(t.charAt(i));
        }
        String a = characterList.stream().sorted().map(String::valueOf).collect(Collectors.joining(""));
        String b = characterLists.stream().sorted().map(String::valueOf).collect(Collectors.joining(""));
        if (Objects.equals(a, b)) {
            return true;
        }
        return false;
    }

    public static boolean isAnagram1(String s, String t) {
        if (null == s || null == t || s == "" || t == "") {
            return false;
        }
        Map<Character, Integer> aMap = new HashMap<>();
        Map<Character, Integer> bMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            aMap.merge(s.charAt(i), 1, (v1, v2) -> v1 + v2);
        }
        for (int i = 0; i < t.length(); i++) {
            bMap.merge(t.charAt(i), 1, (v1, v2) -> v1 + v2);
        }
        if (aMap.size() != bMap.size()) {
            return false;
        }
        for (Map.Entry<Character, Integer> entry : aMap.entrySet()) {
            if (bMap.containsKey(entry.getKey()) && bMap.get(entry.getKey()).equals(entry.getValue())) {
                continue;
            }
            return false;
        }
        return true;
    }
}
